package com.base.binarytree.dictionarytree;

/**
 * 677. 键值映射
 *实现一个 MapSum 类，支持两个方法，insert和sum：
 *
 * MapSum() 初始化 MapSum 对象
 * void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
 * int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/map-sum-pairs
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author leon
 * @date 2021年11月15日 18:49
 */
public class MapSum {
    class Node{
        Node[] nexts = new Node[26];
        int value;
    }
    private Node root;
    public MapSum() {
        root = new Node();
        root.value = 0;
    }

    public void insert(String key, int val) {
        Node root = this.root;
        if (key.length() == 0){
            return;
        }
        char[] chars = key.toCharArray();
        for (char a : chars) {
            if (root.nexts[a-'a']==null){
                Node node = new Node();
                node.value=0;
                root.nexts[a-'a'] = node;
            }
            root = root.nexts[a-'a'];
        }
        root.value = val;
    }

    public int sum(String prefix) {
        Node root =this.root;
        if (prefix.length()==0){
            return 0;
        }
        char[] chars = prefix.toCharArray();
        for (char a: chars) {
            root = root.nexts[a-'a'];
            if (root==null){
                return 0;
            }

        }
        return dfs(root);

    }

    /**
     * 深度遍历
     * @param root
     * @return
     */
    public int dfs(Node root){
        if (root == null){
            return 0;
        }
        int sum = root.value;

        for (int i = 0; i < 26; i++) {
            sum+=dfs(root.nexts[i]);
        }
        return sum;
    }

    public static void main(String[] args) {
        MapSum mapSum = new MapSum();
        mapSum.insert("apple",3);
        System.out.println(mapSum.sum("ap"));
        mapSum.insert("app",2);
        mapSum.insert("apple",2);
        System.out.println(mapSum.sum("ap"));
    }
}
